package leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-03 20:42
 **/
public class LeetCode337 {

    /*//记录抢某个节点情况下的可以抢的最大价值
    Map<TreeNode, Integer> f = new HashMap<>();

    //记录不抢某个节点情况下的可以抢的最大价值
    Map<TreeNode, Integer> g = new HashMap<>();

    public int rob(TreeNode root) {
        //深度优先遍历
        dfs(root);
        //返回抢根节点和不抢根节点中能获取的最大价值
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }

        dfs(root.left);
        dfs(root.right);

        //记录抢root节点能够获取的最大价值,即root.val + g(l)+g(r)
        f.put(root, root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
        //记录不抢root节点能够获取的最大价值,即g(o)=max{f(l),g(l)}+max{f(r),g(r)}。
        g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) + Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));
    }*/


    //优化版本
    public int rob(TreeNode root) {
        //深度优先遍历
        int[] price = dfs(root);
        //返回抢根节点和不抢根节点中能获取的最大价值
        return Math.max(price[0], price[1]);
    }

    int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }

        int[] price = new int[2];
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);

        //记录抢root节点能够获取的最大价值,即root.val + g(l)+g(r)
        price[0] = root.val + l[1] + r[1];
        //记录不抢root节点能够获取的最大价值,即g(o)=max{f(l),g(l)}+max{f(r),g(r)}。
        price[1] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return price;
    }



}
